package com.leetcode.study.suixianglu;

import java.util.Arrays;

/**
 * 将升序的数组中的每个元素平方后，再将数组升序排序
 */
public class ArrayElementSquare {

    public static void main(String[] args) {

        int[] arr = {-2, 1, 2, 3, 4};
        System.out.println(">>>>>> 平方前数组： " + Arrays.toString(arr));
        int[] arr0 = {-2, 1, 2, 3, 4};
        solve0(arr0);
        int[] newArr1 = solve1(arr);
        System.out.println(">>>>>> solve0平方后数组： " + Arrays.toString(arr0));
        System.out.println(">>>>>> solve1平方后数组： " + Arrays.toString(newArr1));
    }

    /**
     * 先将每个数组的元素平方，再通过快排排序，时间复杂度O(n log(n))
     * @param arr
     */
    public static void solve0(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int var0 = arr[i];
            arr[i] = var0 * var0;
        }

        quickSort(arr, 0, arr.length - 1);
    }


    private static void quickSort(int[] arr, int left , int right) {
        // 递归出口, 当两个指针相等时，要把left作为基准值，那right也是基准值，本方法比的是基准值之外的其他值，来确定基准值的坐标
        // 当left == right时，也要终止递归
        if (left >= right) {
            return;
        }

        int baseValuePosition = comparePosition(arr, left, right);

        // 基准值坐标已经确定，对基准值的左边和右边数组即可
        quickSort(arr, 0, baseValuePosition - 1);
        quickSort(arr, baseValuePosition + 1, right);
    }

    /**
     * 获取基准值坐标。
     * 先选定基准值，比如left作为基准值，那就是right以此向前比较找基准值坐标，全部比较完成酒吧基准值放到对应坐标，并返回下标
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private static int comparePosition (int[] arr, int left , int right) {
        // 取左边的值为基准值
        int baseValue = arr[left];

        // 假设基准值下标为最大坐标
        int pos = right;

        // 依次和基准值比较大小
        // 当对应的值>基准值时，要将其往右放
        for (int i = right; i > left; i--) {
            int var = arr[i];

            // [54,32,67,45,65,12,14] 如果 i = 3时，pos=5，将小标3和5互换[54,32,67,45,14,12,65]，将找到大于基准值的数值，往后放，然后将pos--向前移动
            if (var > baseValue) {
                arr[i] = arr[pos];
                arr[pos] = var;
                pos--;
            }
        }

        // 将基准值放到对应的下标, 本来放在的left坐标
        arr[left] = arr[pos];
        arr[pos] = baseValue;
        return pos;
    }

    /**
     * 有序数组中，平方之后最大的值都在数组的两端，所以要从数组的两端，往中间汇聚。
     * 通过双指针：
     * i指针：数组中最小的元素的下标
     * j指针：数组中最大的元素的下标
     * @param arr
     */
    public static int[] solve1(int[] arr) {
        // 用于保存结果的数组
        int[] resultArr = new int[arr.length];

        // 因为要从小到大排序，所以从大（最后）往前放，那么结果就是从小到大排序
        int newSize = arr.length - 1;

        // 当 i > j时，整个数组已经遍历完了一遍。所以只要 i <= j则满足循环条件
        for (int i = 0, j = arr.length - 1; i <= j; ) {
            int var0 = arr[i] * arr[i];
            int var1 = arr[j] * arr[j];

            // 当最小的指针对应的值大于最大的值，那么对应的值要交换
            // [25,1,4,9,16] ==> i=0,j=4; 将25放入新数组，然后i++，比较下一个元素
            if (var0 > var1) {
                // 将最大的值放到新数组中，放完再将指针往前移动，newSize--
                resultArr[newSize--] = var0;
                // 将指针后移
                i++;
            }
            // 当小于等于时，放入j指向的元素，等于时放谁都行
            // [4,1,4,9,16] ==> i=0,j=4; 将16放入新数组，然后j--，比较下一个元素
            else {
                // 将最大的值放到新数组中，放完再将指针往前移动，newSize--
                resultArr[newSize--] = var1;
                // 将指针前移
                j--;
            }
        }
        return resultArr;
    }

}
